package com.fanshuai.algorithms.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 全排列问题
 */
public class Permute {

    public List<List<Integer>> permute(int[] a) {
        List<List<Integer>> combines = new ArrayList<>();

        permute(a, new ArrayList<>(), combines);
        return combines;
    }

    public List<int[]> permute2(int[] a) {
        List<int[]> permutes = new ArrayList<>();

        permute(a, 0, permutes);
        return permutes;
    }

    /**
     * 解法1
     * @param a
     * @param path
     * @param permutes
     */
    private void permute(int[] a, List<Integer> path, List<List<Integer>> permutes) {
        if (path.size() == a.length) {
            permutes.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < a.length; i++) {
            if (!path.contains(a[i])) {
                path.add(a[i]);
                permute(a, path, permutes);
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 解法2
     * @param a
     * @param i
     * @param permute
     */
    private void permute(int[] a, int i, List<int[]> permute) {
        if (i == a.length) {
            int[] arr = new int[a.length];
            System.arraycopy(a, 0, arr, 0, a.length);
            permute.add(arr);
            return;
        }

        for (int j = i; j < a.length; j++) {
            swap(a, i, j);
            permute(a, i + 1, permute);
            swap(a, i, j);
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
